package top.lywivan.linkedlist;

import top.lywivan.linkedlist.inf.List;

/**
 * @author :lyw.ivan
 * @date :Created in 2022/5/28
 * @description :
 * @version: 1.0
 */
public class LinkedList<E> implements List<E> {

    //链表大小
    private int size;

    //链表头结点
    private Node<E> head;

    //链表尾结点
    private Node<E> last;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public int indexOf(E o) {
        //定义局部变量
        int index=0;
        //根据参数是否为null分为不同的情况
        if (o==null){
            //遍历链表
            for (Node<E> first=head;first!=null;first=first.next){
                if (first.val==o){
                    return index;
                }
                index++;
            }
        }else {
            //遍历链表
            for (Node<E> first=head;first!=null;first=first.next){
                if (first.val.equals(o)){
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(E e) {
        //调用indexOf即可
        return indexOf(e)>-1;
    }

    @Override
    public boolean add(E e) {
        //将元素添加到链表尾部
        linkLast(e);
        return true;
    }

    private void linkLast(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(e,l , null);
        last=newNode;

        if (l==null){
            //如果为空链表，则将新元素设置为头结点
            head=newNode;
        }else {
            //否则将原来的下一指针指向新结点
            l.next=newNode;
        }
        size++;
    }

    @Override
    public void add(int index, E element) {
        //判断索引是否有效
        checkIndex(index);
        if (index==size){
            //添加到末尾
            this.add(element);
        }else {
            //添加到指定索引处
            linkBefore(index,element);
        }
    }

    private void linkBefore(int index, E element) {
        //获取index处原来的结点
        Node<E> n = node(index);
        //获取原来结点的前一个结点
        Node<E> prev=n.prev;
        //创建当前结点
        Node<E> newNode = new Node<>(element, prev, n);
        n.prev=newNode;
        //判断是否为插入头结点
        if (prev==null){
            head=newNode;
        }else {
            prev.next=newNode;
        }
        size++;
    }

    private Node<E> node(int index) {
        //根据索引和size的关系判断从那边遍历效率高
        if (index<(size>>1)){
            //重新拿一遍头结点
            Node<E> result=head;
            //从头开始遍历
            for (int i=0;i<index;i++){
                result=result.next;
            }
            return result;
        }else {
            //重新拿一遍尾结点
            Node<E> result=last;
            //从头开始遍历
            for (int i=size-1;i>index;i--){
                result=result.prev;
            }
            return result;
        }
    }

    private void checkIndex(int index) {
        if (index<0||index>size){
            throw new IndexOutOfBoundsException("index out of bounds,index="+index+",size="+size);
        }
    }

    @Override
    public E set(int index, E element) {
        //判断索引是否有效
        isElementIndex(index);
        //获取原来的结点
        Node<E> node = node(index);
        E beforeVal=node.val;
        node.val=element;
        return beforeVal;
    }

    private void isElementIndex(int index) {
        if (index<0||index>=size){
            throw new IndexOutOfBoundsException("index out of bounds,index="+index+",size="+size);
        }
    }

    @Override
    public E get(int index) {
        //判断索引是否有效
        isElementIndex(index);
        return node(index).val;
    }

    @Override
    public E remove(int index) {
        //判断索引是否有效
        isElementIndex(index);
        return unlink(index);
    }

    private E unlink(int index) {
        //获取原先结点
        Node<E> oldNode = node(index);
        //获取前后结点
        Node<E> prevNode = oldNode.prev;
        Node<E> nextNode = oldNode.next;
        E oldVal = oldNode.val;
        oldNode.val=null;
        //判断是否为头结点
        if (prevNode==null){
            head=nextNode;
        }else {
            prevNode.next=nextNode;
            oldNode.prev=null;
        }
        //判断是否是尾结点
        if (nextNode==null){
            last=prevNode;
        }else {
            nextNode.prev=prevNode;
            oldNode.next=null;
        }
        size--;
        return oldVal;
    }

    @Override
    public void clear() {
        //遍历链表，取消原来的地址关系
        for (Node<E> n=head;n!=null;){
            //先记录下一结点
            Node<E> next=n.next;
            n.val=null;
            n.next=null;
            n.prev=null;
            n=next;
        }
        //设置头尾结点为null
        head=null;
        last=null;
        size=0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node<E> node=head;node!=null;node=node.next){
            sb.append(node.val).append("->");
        }
        return sb.append("NULL").toString();
    }

    /**
     * 定义链表结点的静态内部类
     * @param <E>
     */
    private static class Node<E>{
        E val;
        Node<E> prev;
        Node<E> next;

        //定义构造
        public Node(E val, Node<E> prev, Node<E> next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
}
